package org.leetcode.middle.leetcode106;

import org.leetcode.TreeNode;

public class Solution {


    public TreeNode buildTree2(int[] inorder, int[] postorder){

        if (inorder.length==0 || postorder.length==0){
            return null;
        }

        return buildHelper2(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }


     private TreeNode buildHelper2(int [] inorder,int inStart,int inEnd,int [] postorder,int postStart,int postEnd){

        if (postStart>postEnd){
            return null;
        }

        int val = postorder[postEnd];
        TreeNode root = new TreeNode(val);

        int midIndex;

         for ( midIndex = inStart; midIndex <=inEnd; midIndex++) {
             if (inorder[midIndex]==val){
                 break;
             }
         }

         int inLeftStart=inStart;
         int inLeftEnd = midIndex-1;

         int leftLength = inLeftEnd-inLeftStart;

         int inRightStart = midIndex+1;
         int inRightEnd = inEnd;

         int postLeftStart = postStart;
         int postLeftEnd =postStart+leftLength;

         int postRightStart = postLeftEnd+1;
         int postRightEnd=postEnd-1;

         root.left=buildHelper2(inorder,inLeftStart,inLeftEnd,postorder,postLeftStart,postLeftEnd);

         root.right=buildHelper2(inorder,inRightStart,inRightEnd,postorder,postRightStart,postRightEnd);

         return root;

     }

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if(postorder.length == 0 || inorder.length == 0)
            return null;
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
        if(postorderStart == postorderEnd)
            return null;
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){
            if(inorder[middleIndex] == rootVal)
                break;
        }

        int leftInorderStart = inorderStart;
        int leftInorderEnd = middleIndex;
        int rightInorderStart = middleIndex + 1;
        int rightInorderEnd = inorderEnd;


        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);
        int rightPostorderStart = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;
        root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd,  postorder, leftPostorderStart, leftPostorderEnd);
        root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);

        return root;
    }
}
